#include "mySearch.h"
#include <iostream>
#include <string>


using namespace std;

SSTable::SSTable()
{
	length = 0;
	origin = NULL;
}

SSTable::SSTable(int length, int* origin)
{
	this->length = length;
	this->origin = origin;
}

SSTable::~SSTable()
{
	length = 0;
	if (!origin) {
		delete[]origin; origin = NULL;
	}
}

int SSTable::getLength()
{
	return length;
}

int* SSTable::getOrigin()
{
	return origin;
}

void SSTable::setLength(int length)
{
	this->length = length;
}

void SSTable::setOrigin(int* origin)
{
	this->origin = origin;
}

int SSTable::binSearch(int val)
{
	int low = 0, high = length, mid = length / 2;
	while (low != high)
	{
		if (origin[mid] == val)break;
		else if (origin[mid] < val)
			low = mid + 1;
		else high = mid - 1;
		mid = (low + high) / 2;
	}
	if (origin[mid] == val)return mid;
	else return -1;
}

BSTreeNode::BSTreeNode()
{
	data = 0;
	lchild = NULL;
	rchild = NULL;
}

BSTreeNode::BSTreeNode(int data)
{
	this->data = data;
	lchild = NULL; rchild = NULL;
}

BSTreeNode::BSTreeNode(int data, BSTreeNode* lchild, BSTreeNode* rchild)
{
	this->data; this->lchild = lchild; this->rchild;
}

BSTreeNode::~BSTreeNode()
{
	data = 0;
	if (rchild) {
		delete rchild; rchild = NULL;
	}
	if (lchild) {
		delete lchild; lchild = NULL;
	}
}

int BSTreeNode::getData()
{
	return data;
}

BSTreeNode* BSTreeNode::getLChild()
{
	return lchild;
}

BSTreeNode* BSTreeNode::getRChild()
{
	return rchild;
}

void BSTreeNode::setData(int data)
{
	this->data = data;
}

void BSTreeNode::setLChild(BSTreeNode* lchild)
{
	this->lchild = lchild;
}

void BSTreeNode::setRChild(BSTreeNode* rchild)
{
	this->rchild = rchild;
}

BSTree::BSTree()
{
	num = 0;
	root = NULL;
}

BSTree::BSTree(int num, int* data)
{
	this->num = num;
	BSTreeNode* cur;
	if (num)root = new BSTreeNode(data[0]);
	for (int i = 1; i < num; i++)
	{
		BSTreeNode* now = new BSTreeNode(data[i]);
		cur = root;
		while (cur) {
			if (data[i] > cur->getData())
				if (!cur->getRChild()) {
					cur->setRChild(now); break;
				}
				else cur = cur->getRChild();
			else if (!cur->getLChild()) {
				cur->setLChild(now); break;
			}
			else cur = cur->getLChild();
		}
	}
}

BSTree::~BSTree()
{
	num = 0;
	if (root) {
		delete root; root = NULL;
	}
}

int BSTree::getNum()
{
	return num;
}

BSTreeNode* BSTree::getRoot()
{
	return root;
}

void BSTree::setNum(int num)
{
	this->num = num;
}

void BSTree::setRoot(BSTreeNode* root)
{
	this->root = root;
}

void printTemp(BSTreeNode* cur, string& result) {
	if (!cur)return;
	result += to_string(cur->getData());
	result.push_back(' ');
	printTemp(cur->getLChild(), result);
	printTemp(cur->getRChild(), result);
}
string BSTree::printTree()
{
	string result;
	printTemp(root, result);
	return result;
}

bool BSTree::searchNode(int val) {
	BSTreeNode* cur = root;
	while (cur) {
		if (val > cur->getData())cur = cur->getRChild();
		else if (val < cur->getData())cur = cur->getLChild();
		else return 1;
	}
	return 0;
}


bool BSTree::addNode(int val)
{
	BSTreeNode* cur = root;
	BSTreeNode* now = new BSTreeNode(val);
	while (cur) {
		if (val > cur->getData())
			if (cur->getRChild())cur = cur->getRChild();
			else {
				cur->setRChild(now); break;
			}
		else if (val < cur->getData())
			if (cur->getLChild())cur = cur->getLChild();
			else {
				cur->setLChild(now); break;
			}
		else {
			delete now;
			return 0;
		}
	}
	return 1;
}

bool BSTree::deleteNode(int val)
{
	BSTreeNode* cur = root, * fro = root;
	while (cur) {
		if (val > cur->getData()) {
			fro = cur; cur = cur->getRChild();
		}
		else if (val < cur->getData()) {
			fro = cur; cur = cur->getLChild();
		}
		else break;
	}
	if (!cur)return 0;
	if (!cur->getLChild() && !cur->getRChild()) {
		if (fro->getLChild() == cur)fro->setLChild(NULL);
		else fro->setRChild(NULL);
		delete cur;
	}
	else if (!cur->getLChild() && cur->getRChild()) {
		fro->setRChild(cur->getRChild());
		delete cur;
	}
	else if (cur->getLChild() && !cur->getRChild()) {
		fro->setLChild(cur->getLChild());
		delete cur;
	}
	else {
		BSTreeNode* Fro = cur->getLChild();
		fro = cur;
		while (Fro->getRChild()) {
			fro = Fro; Fro = Fro->getRChild();
		}
		cur->setData(Fro->getData());
		fro->setRChild(Fro->getLChild());
		delete Fro;
	}
	return 1;
}